{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Average Pass Ratio"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAverageRatio"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大平均通过率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 <code>classes</code> ，其中 <code>classes[i] = [pass<sub>i</sub>, total<sub>i</sub>]</code> ，表示你提前知道了第 <code>i</code> 个班级总共有 <code>total<sub>i</sub></code> 个学生，其中只有 <code>pass<sub>i</sub></code> 个学生可以通过考试。</p>\n",
    "\n",
    "<p>给你一个整数 <code>extraStudents</code> ，表示额外有 <code>extraStudents</code> 个聪明的学生，他们 <strong>一定</strong> 能通过任何班级的期末考。你需要给这 <code>extraStudents</code> 个学生每人都安排一个班级，使得 <strong>所有</strong> 班级的 <strong>平均</strong> 通过率 <strong>最大</strong> 。</p>\n",
    "\n",
    "<p>一个班级的 <strong>通过率</strong> 等于这个班级通过考试的学生人数除以这个班级的总人数。<strong>平均通过率</strong> 是所有班级的通过率之和除以班级数目。</p>\n",
    "\n",
    "<p>请你返回在安排这 <code><span style=\"\">extraStudents</span></code> 个学生去对应班级后的 <strong>最大</strong> 平均通过率。与标准答案误差范围在 <code>10<sup>-5</sup></code> 以内的结果都会视为正确结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>classes = [[1,2],[3,5],[2,2]], <code>extraStudents</code> = 2\n",
    "<b>输出：</b>0.78333\n",
    "<b>解释：</b>你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>classes = [[2,4],[3,9],[4,5],[2,10]], <code>extraStudents</code> = 4\n",
    "<strong>输出：</strong>0.53485\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= classes.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>classes[i].length == 2</code></li>\n",
    "\t<li><code>1 <= pass<sub>i</sub> <= total<sub>i</sub> <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= extraStudents <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-average-pass-ratio](https://leetcode.cn/problems/maximum-average-pass-ratio/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-average-pass-ratio](https://leetcode.cn/problems/maximum-average-pass-ratio/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[3,5],[2,2]]\\n2', '[[2,4],[3,9],[4,5],[2,10]]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        # n = len(classes)\n",
    "        # for i in range(extraStudents):\n",
    "        #     increase = 0\n",
    "        #     index = 0\n",
    "        #     for x in range(len(classes)):\n",
    "        #         temp = (classes[x][0] + 1)/(classes[x][1] + 1) - classes[x][0]/classes[x][1]\n",
    "        #         if temp > increase:\n",
    "        #             increase = temp\n",
    "        #             index = x\n",
    "        #     classes[index][0] += 1\n",
    "        #     classes[index][1] += 1\n",
    "        # ans = sum(x[0]/x[1] for x in classes)\n",
    "        # return ans/n\n",
    "\n",
    "        n = len(classes)\n",
    "        max_heap = []\n",
    "        \n",
    "        for c in classes:\n",
    "            heapq.heappush(max_heap, (-((c[0]+1)/(c[1]+1) - c[0]/c[1]), c))\n",
    "        \n",
    "        for _ in range(extraStudents):\n",
    "            _, c = heapq.heappop(max_heap)\n",
    "            c[0] += 1\n",
    "            c[1] += 1\n",
    "            heapq.heappush(max_heap, (-((c[0]+1)/(c[1]+1) - c[0]/c[1]), c))\n",
    "        \n",
    "        ans = sum(c[0]/c[1] for _, c in max_heap)\n",
    "        return ans/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        q = []\n",
    "        for a, b in classes:\n",
    "            heappush(q, [(a - b) / (b * (b + 1)), a, b])\n",
    "        while extraStudents:\n",
    "            extraStudents -= 1\n",
    "            r, a, b = heappop(q)\n",
    "            a += 1\n",
    "            b += 1\n",
    "            heappush(q, [(a - b) / (b * (b + 1)), a, b])\n",
    "        ret = sum(x[1] / x[2] for x in q)\n",
    "        return ret / len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        q = []\n",
    "        for p, t in classes:\n",
    "            a, b = p + 1, t + 1\n",
    "            heapq.heappush(q, (p / t - a / b, p, t))\n",
    "        \n",
    "        for _ in range(extraStudents):\n",
    "            _, p, t = heapq.heappop(q)\n",
    "            p += 1\n",
    "            t += 1\n",
    "            a, b = p + 1, t + 1\n",
    "            heapq.heappush(q, (p / t - a / b, p, t))\n",
    "\n",
    "        return sum(x[1] / x[2] for x in q) / len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        import heapq\n",
    "        classes = [(c[0]/c[1] - (c[0]+1)/(c[1]+1), c[0], c[1]) for c in classes]\n",
    "        heapq.heapify(classes)\n",
    "        while extraStudents:\n",
    "            p = heapq.heappop(classes)\n",
    "            heapq.heappush(classes, ((p[1]+1)/(p[2]+1) - (p[1]+2)/(p[2]+2), p[1]+1, p[2]+1))\n",
    "            extraStudents -= 1\n",
    "        return sum(c[1]/c[2] for c in classes) / len(classes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        diff = lambda x, y: (x + 1) / (y + 1) - x / y\n",
    "\n",
    "        q = list()\n",
    "        ans = 0\n",
    "        for x, y in classes:\n",
    "            q.append((-diff(x, y), x, y))\n",
    "            ans += x / y\n",
    "        heapify(q)\n",
    "\n",
    "        for _ in range(extraStudents):\n",
    "            d, x, y = heappop(q)\n",
    "            ans += -d\n",
    "            heappush(q, (-diff(x + 1, y + 1), x+1, y+1))\n",
    "        \n",
    "        return ans / len(classes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 来个小顶堆，分子分母相差最小的\n",
    "# 直接数学思路得了\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        def rise(x,y):\n",
    "            return (y-x)/(y*(y+1))\n",
    "        heap = []\n",
    "        res = 0 \n",
    "        for i,j in classes:\n",
    "            ri = rise(i,j)\n",
    "            res += i/j\n",
    "            heap.append((-ri,i,j))\n",
    "        heapq.heapify(heap)\n",
    "        \n",
    "        while extraStudents > 0:\n",
    "            r,i,j = heapq.heappop(heap)\n",
    "            res -= r \n",
    "            ri = rise(i+1,j+1)\n",
    "            heapq.heappush(heap,(-ri,i+1,j+1))\n",
    "            extraStudents -= 1\n",
    "        return res/len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        diff = lambda x, y: (x + 1) / (y + 1) - x / y\n",
    "        \n",
    "        q = list()\n",
    "        ans = 0.\n",
    "        for x, y in classes:\n",
    "            ans += x / y\n",
    "            # python 中的优先队列是小根堆，所以要对增加量取相反数，达到大根堆的效果\n",
    "            q.append((-diff(x, y), x, y))\n",
    "        \n",
    "        heapq.heapify(q)\n",
    "        \n",
    "        for _ in range(extraStudents):\n",
    "            d, x, y = heapq.heappop(q)\n",
    "            ans += -d\n",
    "            heapq.heappush(q, (-diff(x + 1, y + 1), x + 1, y + 1))\n",
    "        \n",
    "        return ans / len(classes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = []\n",
    "        for p, t in classes:\n",
    "            rate = p / t - (p+1) / (t+1)\n",
    "            heappush(h, [rate, p, t])\n",
    "        # print(h)\n",
    "        for i in range(extraStudents):\n",
    "            r, p, t = heappop(h)\n",
    "            newR = (p + 1) / (t + 1) - (p+2) / (t+2)\n",
    "            heappush(h, [newR, p + 1, t + 1])\n",
    "            # print(h)\n",
    "        n = len(h)\n",
    "        cur = 0\n",
    "        for _, p, t in h:\n",
    "            cur += p / t\n",
    "        return cur / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        heap = []\n",
    "        for p, t in classes:\n",
    "            heap.append([-((p + 1.0) / (t + 1.0) - p * 1.0 / t), p, t])\n",
    "        heapq.heapify(heap)\n",
    "        for index in range(extraStudents):\n",
    "            rate, p, t = heapq.heappop(heap)\n",
    "            p += 1\n",
    "            t += 1\n",
    "            heapq.heappush(heap, [-((p + 1.0) / (t + 1.0) - p * 1.0 / t), p, t])\n",
    " \n",
    "        s = 0\n",
    "        for rate, p, t in heap:\n",
    "            s += p * 1.0 / t\n",
    "        return s / len(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        heap = []\n",
    "        for a, b in classes:\n",
    "            heappush(heap, [-(a+1)/(b+1)+a/b, a, b])\n",
    "        while(extraStudents > 0):\n",
    "            _, a, b = heappop(heap)\n",
    "            a += 1\n",
    "            b += 1\n",
    "            heappush(heap, [-(a+1)/(b+1)+a/b, a, b])\n",
    "            extraStudents -= 1\n",
    "        result = 0\n",
    "        for _, a, b in heap:\n",
    "            result += a/b \n",
    "        return result/len(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        pq = []\n",
    "        for i, (p, t) in enumerate(classes):\n",
    "            heappush(pq, (p / t - (p + 1) / (t + 1), i))\n",
    "\n",
    "        dis = [0] * len(classes)\n",
    "        for _ in range(extraStudents):\n",
    "            diff, i = heappop(pq)\n",
    "            dis[i] += 1\n",
    "            p, t = classes[i]\n",
    "            heappush(pq, ((p + dis[i]) / (t + dis[i]) - (p + dis[i] + 1) / (t + dis[i] + 1) ,i))\n",
    "\n",
    "        ans = 0\n",
    "        for i, (p, t) in enumerate(classes):\n",
    "            ans += (p + dis[i]) / (t + dis[i])\n",
    "        return ans / len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = []\n",
    "        for b, a in classes:\n",
    "            h.append(((b - a) / (a * a + a), a, b))\n",
    "        heapq.heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            r, a, b = heapq.heappop(h)\n",
    "            a += 1\n",
    "            b += 1\n",
    "            heapq.heappush(h, ((b - a) / (a * a + a), a, b))\n",
    "        ans = 0\n",
    "        for _, a, b in h:\n",
    "            ans += b / a\n",
    "        return ans / len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        # def IncreaseRate(x,y):\n",
    "        #     return (x+1)/(y+1)-x/y\n",
    "        IncreaseRate = lambda x,y:(x+1)/(y+1)-x/y\n",
    "        q = []\n",
    "        ans = 0\n",
    "        # 利用最小堆存储 （-通过率,x,y）\n",
    "        for x,y in classes:\n",
    "            ans += x/y \n",
    "            q.append((-IncreaseRate(x,y),x,y))\n",
    "        # 将列表变成堆\n",
    "        heapq.heapify(q)\n",
    "        for _ in range(extraStudents):\n",
    "            v,x,y = heapq.heappop(q)\n",
    "            ans += -v\n",
    "            heapq.heappush(q,(-IncreaseRate(x+1,y+1),x+1,y+1))\n",
    "        return ans/len(classes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        c = [((i/j)-(i+1)/(j+1), (i, j)) for i, j in classes]\n",
    "        heapq.heapify(c)\n",
    "\n",
    "        for i in range(extraStudents):\n",
    "            _, stu = heapq.heappop(c)\n",
    "            heapq.heappush(c, ((((stu[0]+1)/(stu[1]+1))-((stu[0]+2)/(stu[1]+2))), (stu[0]+1, stu[1]+1)))\n",
    "        \n",
    "        ans = 0\n",
    "        for _, x in c:\n",
    "            ans += (x[0] / x[1])\n",
    "        return ans / len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        rank, n = [[(c[0] - c[1]) / (c[1] ** 2 + c[1])] + c for c in classes], len(classes)\n",
    "        heapify(rank)\n",
    "        for s in range(extraStudents):\n",
    "            c = heappop(rank)\n",
    "            a, b = c[1] + 1, c[2] + 1\n",
    "            c = [(a - b) / (b ** 2 + b), a, b]\n",
    "            heappush(rank, c)\n",
    "        return sum(r[1] / r[2] for r in rank) / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            _, a, b = heappop(h)\n",
    "            a, b = a + 1, b + 1\n",
    "            heappush(h, (a / b - (a + 1) / (b + 1), a, b))\n",
    "        return sum(v[1] / v[2] for v in h) / len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        # n = len(classes)\n",
    "        # for i in range(extraStudents):\n",
    "        #     increase = 0\n",
    "        #     index = 0\n",
    "        #     for x in range(len(classes)):\n",
    "        #         temp = (classes[x][0] + 1)/(classes[x][1] + 1) - classes[x][0]/classes[x][1]\n",
    "        #         if temp > increase:\n",
    "        #             increase = temp\n",
    "        #             index = x\n",
    "        #     classes[index][0] += 1\n",
    "        #     classes[index][1] += 1\n",
    "        # ans = sum(x[0]/x[1] for x in classes)\n",
    "        # return ans/n\n",
    "\n",
    "        # n = len(classes)\n",
    "        # max_heap = []\n",
    "        \n",
    "        # for c in classes:\n",
    "        #     heapq.heappush(max_heap, (-((c[0]+1)/(c[1]+1) - c[0]/c[1]), c))\n",
    "        \n",
    "        # for _ in range(extraStudents):\n",
    "        #     _, c = heapq.heappop(max_heap)\n",
    "        #     c[0] += 1\n",
    "        #     c[1] += 1\n",
    "        #     heapq.heappush(max_heap, (-((c[0]+1)/(c[1]+1) - c[0]/c[1]), c))\n",
    "        \n",
    "        # ans = sum(c[0]/c[1] for _, c in max_heap)\n",
    "        # return ans/n\n",
    "\n",
    "        n = len(classes)\n",
    "        max_heap = []\n",
    "        \n",
    "        # 定义元素的优先级并插入优先队列\n",
    "        for c in classes:\n",
    "            priority = -((c[0]+1)/(c[1]+1) - c[0]/c[1])\n",
    "            heapq.heappush(max_heap, (priority, c))\n",
    "        \n",
    "        # 处理额外学生\n",
    "        for _ in range(extraStudents):\n",
    "            _, c = heapq.heappop(max_heap)  # 弹出最大优先级的元素\n",
    "            c[0] += 1  # 更新班级信息\n",
    "            c[1] += 1\n",
    "            priority = -((c[0]+1)/(c[1]+1) - c[0]/c[1])  # 计算更新后的优先级\n",
    "            heapq.heappush(max_heap, (priority, c))  # 插入优先队列\n",
    "        \n",
    "        # 计算最终结果\n",
    "        ans = sum(c[0]/c[1] for _, c in max_heap)\n",
    "        return ans/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        rank, n = [[(c[0] - c[1]) / (c[1] ** 2 + c[1])] + c for c in classes], len(classes)\n",
    "        heapify(rank)\n",
    "        for _ in range(extraStudents):\n",
    "            c = heappop(rank)\n",
    "            a, b = c[1] + 1, c[2] + 1\n",
    "            heappush(rank, [(a - b) / (b ** 2 + b), a, b])\n",
    "        return sum(r[1] / r[2] for r in rank) / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            _, a, b = heappop(h)\n",
    "            a, b = a + 1, b + 1\n",
    "            heappush(h, (a / b - (a + 1) / (b + 1), a, b))\n",
    "        return sum(v[1] / v[2] for v in h) / len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [(a/b-(a+1)/(b+1),a,b) for a,b in classes]\n",
    "        heapify(h)\n",
    "        for i in range(extraStudents):\n",
    "            i,a,b = heappop(h)\n",
    "            a,b = a+1,b+1\n",
    "            heappush(h,(a/b-(a+1)/(b+1),a,b))\n",
    "        return sum(x[1]/x[2] for x in h)/len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        # 思维层面\n",
    "        \n",
    "        # 代码层面\n",
    "        diff = lambda x,y:(x+1)/(y+1)-x/y\n",
    "        q = []\n",
    "        ans = 0\n",
    "        for x,y in classes:\n",
    "            ans += x/y\n",
    "            q.append((-diff(x,y),x,y))\n",
    "        heapq.heapify(q)\n",
    "        for _ in range(extraStudents):\n",
    "            d,x,y = heapq.heappop(q)\n",
    "            ans += -d\n",
    "            heapq.heappush(q,(-diff(x+1,y+1),x+1,y+1))\n",
    "        return ans/len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Entry:\n",
    "    __slots__ = 'p', 't'\n",
    "\n",
    "    def __init__(self, p: int, t: int):\n",
    "        self.p = p\n",
    "        self.t = t\n",
    "\n",
    "    def __lt__(self, b: 'Entry') -> bool:\n",
    "        return (self.t - self.p) * b.t * (b.t + 1) > (b.t - b.p) * self.t * (self.t + 1)\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [Entry(*c) for c in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            heapreplace(h, Entry(h[0].p + 1, h[0].t + 1))\n",
    "        return sum(e.p / e.t for e in h) / len(h)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        heap = []\n",
    "        for a, b in classes:\n",
    "            heappush(heap, [-(a+1)/(b+1)+a/b, a, b])\n",
    "        while(extraStudents > 0):\n",
    "            _, a, b = heappop(heap)\n",
    "            a += 1\n",
    "            b += 1\n",
    "            heappush(heap, [-(a+1)/(b+1)+a/b, a, b])\n",
    "            extraStudents -= 1\n",
    "        result = 0\n",
    "        for _, a, b in heap:\n",
    "            result += a/b \n",
    "        return result/len(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        \n",
    "        # 定义一个函数，计算给定班级增加一个学生会带来的通过率增益\n",
    "        def gain(p, t):\n",
    "            return (p+1)/(t+1) - p/t\n",
    "        \n",
    "        # 创建一个优先队列，用于存储每个班级的增益\n",
    "        heap = []\n",
    "        for idx, (p, t) in enumerate(classes):\n",
    "            heapq.heappush(heap, (-gain(p, t), idx))  # 由于Python的heapq只实现了最小堆，我们使用负数来模拟最大堆\n",
    "        \n",
    "        # 将extraStudents个学生分配到增益最大的班级中\n",
    "        for _ in range(extraStudents):\n",
    "            _, idx = heapq.heappop(heap)\n",
    "            classes[idx][0] += 1  # 通过的学生+1\n",
    "            classes[idx][1] += 1  # 总人数+1\n",
    "            p, t = classes[idx]\n",
    "            heapq.heappush(heap, (-gain(p, t), idx))\n",
    "        \n",
    "        # 计算最终的平均通过率\n",
    "        total_ratio = sum(p/t for p, t in classes)\n",
    "        return total_ratio / len(classes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Entry:\n",
    "    __slots__ = 'p', 't'\n",
    "\n",
    "    def __init__(self, p: int, t: int):\n",
    "        self.p = p\n",
    "        self.t = t\n",
    "\n",
    "    def __lt__(self, b: 'Entry') -> bool:\n",
    "        return (self.t - self.p) * b.t * (b.t + 1) > (b.t - b.p) * self.t * (self.t + 1)\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [Entry(*c) for c in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            heapreplace(h, Entry(h[0].p + 1, h[0].t + 1))\n",
    "        return sum(e.p / e.t for e in h) / len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        hp=[]\n",
    "        for i in range(len(classes)):\n",
    "            p,t=classes[i]\n",
    "            heapq.heappush(hp,(p/t-(p+1)/(t+1),i))\n",
    "        while extraStudents:\n",
    "            # print(hp)\n",
    "            r,index=heapq.heappop(hp)\n",
    "            p,t=classes[index]\n",
    "            p+=1\n",
    "            t+=1\n",
    "            classes[index]=[p,t]\n",
    "            heapq.heappush(hp,(p/t-(p+1)/(t+1),index))\n",
    "            extraStudents-=1\n",
    "        # print(classes)\n",
    "        return sum([x[0]/x[1] for x in classes])/len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Entry:\n",
    "    __slots__ = 'p', 't'\n",
    "\n",
    "    def __init__(self, p: int, t: int):\n",
    "        self.p = p\n",
    "        self.t = t\n",
    "\n",
    "    def __lt__(self, b: 'Entry') -> bool:\n",
    "        return (self.t - self.p) * b.t * (b.t + 1) > (b.t - b.p) * self.t * (self.t + 1)\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [Entry(*c) for c in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            heapreplace(h, Entry(h[0].p + 1, h[0].t + 1))\n",
    "        return sum(e.p / e.t for e in h) / len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Entry:\n",
    "    __slots__ = 'p', 't'\n",
    "\n",
    "    def __init__(self, p: int, t: int):\n",
    "        self.p = p\n",
    "        self.t = t\n",
    "\n",
    "    def __lt__(self, b: 'Entry') -> bool:\n",
    "        return (self.t - self.p) * b.t * (b.t + 1) > (b.t - b.p) * self.t * (self.t + 1)\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [Entry(*c) for c in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            heapreplace(h, Entry(h[0].p + 1, h[0].t + 1))\n",
    "        return sum(e.p / e.t for e in h) / len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        def IncreaseRate(x,y):\n",
    "            return (x+1)/(y+1)-x/y\n",
    "        q = []\n",
    "        ans = 0\n",
    "        # 利用最小堆存储 （-通过率,x,y）\n",
    "        for x,y in classes:\n",
    "            ans += x/y \n",
    "            q.append((-IncreaseRate(x,y),x,y))\n",
    "        # 将列表变成堆\n",
    "        heapq.heapify(q)\n",
    "        for _ in range(extraStudents):\n",
    "            v,x,y = heapq.heappop(q)\n",
    "            ans += -v\n",
    "            heapq.heappush(q,(-IncreaseRate(x+1,y+1),x+1,y+1))\n",
    "        return ans/len(classes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            _, a, b = heappop(h)\n",
    "            a, b = a + 1, b + 1\n",
    "            heappush(h, (a / b - (a + 1) / (b + 1), a, b))\n",
    "        return sum(v[1] / v[2] for v in h) / len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        queue = []\n",
    "        for i in range(len(classes)):\n",
    "            heapq.heappush(queue,(-(classes[i][0]+1)/(classes[i][1]+1)+classes[i][0]/classes[i][1],classes[i][0],classes[i][1]))\n",
    "        \n",
    "        while extraStudents>0:\n",
    "            a = heapq.heappop(queue)\n",
    "            heapq.heappush(queue,(-(a[1]+2)/(a[2]+2)+(a[1]+1)/(a[2]+1),a[1]+1,a[2]+1))\n",
    "            extraStudents-=1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(queue)):\n",
    "            ans+=queue[i][1]/queue[i][2]\n",
    "        \n",
    "        return ans/len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "\n",
    "        # heap\n",
    "        arr = []\n",
    "        for p, w in classes:\n",
    "            arr.append([(p/w - (p+1)/(w+1)), p, w])\n",
    "\n",
    "        heapq.heapify(arr)\n",
    "\n",
    "        for _ in range(extraStudents):\n",
    "            r, p, w = heapq.heappop(arr)\n",
    "            p += 1\n",
    "            w += 1\n",
    "            heapq.heappush(arr, [(p/w - (p+1)/(w+1)), p, w])\n",
    "        \n",
    "        # print(arr)\n",
    "        return sum([l[1]/l[2] for l in arr]) / len(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        \n",
    "        stack = [[p/t - (p+1)/(t+1), p, t] for p, t in classes]\n",
    "        heapify(stack)\n",
    "        for _ in range(extraStudents):\n",
    "            _, p, t = heappop(stack)\n",
    "            p += 1\n",
    "            t += 1\n",
    "            heappush(stack, [p/t - (p+1)/(t+1), p, t])\n",
    "        return sum(p/t for _, p, t in stack)/len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "      h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]\n",
    "      heapq.heapify(h)\n",
    "      for _ in range(extraStudents):\n",
    "          _, a, b = heapq.heappop(h)\n",
    "          a, b = a + 1, b + 1\n",
    "          heapq.heappush(h, (a / b - (a + 1) / (b + 1), a, b))\n",
    "      return sum(v[1] / v[2] for v in h) / len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 优先队列 \n",
    "    # O(mlogn) O(m)\n",
    "    # https://leetcode.cn/problems/maximum-average-pass-ratio/solutions/655148/zui-da-ping-jun-tong-guo-lu-by-zerotrac2-84br/\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        diff = lambda x, y: (x + 1) / (y + 1) - x / y\n",
    "        \n",
    "        q = list()\n",
    "        ans = 0.0\n",
    "        for x, y in classes:\n",
    "            ans += x / y\n",
    "            # python 中的优先队列是小根堆，所以要对增加量取相反数，达到大根堆的效果\n",
    "            q.append((-diff(x, y), x, y))\n",
    "        \n",
    "        heapq.heapify(q)\n",
    "        \n",
    "        for _ in range(extraStudents):\n",
    "            d, x, y = heapq.heappop(q)\n",
    "            ans += -d\n",
    "            heapq.heappush(q, (-diff(x + 1, y + 1), x + 1, y + 1))\n",
    "        \n",
    "        return ans / len(classes)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        一个班级的通过率为 a/b\n",
    "        给这个班级安排一个学生 通过率为 a+1/b+1\n",
    "        通过率的增量为 a+1/b+1 - a/b\n",
    "        并且增量是递减的 a+2/b+2 < a+1/b+1 (大根堆)\n",
    "    '''\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            _, a, b = heappop(h)\n",
    "            a, b = a + 1, b + 1\n",
    "            heappush(h, (a / b - (a + 1) / (b + 1), a, b))\n",
    "        return sum(v[1] / v[2] for v in h) / len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Memo:\n",
    "    def __init__(self, p:int, t:int):\n",
    "        self.p = p\n",
    "        self.t = t\n",
    "\n",
    "    def __lt__(self, b: 'Memo') -> bool: #less than, 所以比较时把<改为> ，也就把小根堆改成了大根堆\n",
    "        return (self.t-self.p) * b.t * (b.t+1) > (b.t-b.p) * self.t *(self.t+1)\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [Memo(*c) for c in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            heapreplace(h, Memo(h[0].p + 1, h[0].t + 1))\n",
    "        return sum(e.p / e.t for e in h) / len(h)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        diff = lambda x, y:(x + 1) / (y + 1) - x / y\n",
    "        \n",
    "        q = list()\n",
    "        ans = 0\n",
    "        for x, y in classes:\n",
    "            ans += x / y\n",
    "            q.append((-diff(x, y), x, y))\n",
    "        heapq.heapify(q)\n",
    "\n",
    "        for _ in range(extraStudents):\n",
    "            d, x, y = heappop(q)\n",
    "            ans += -d\n",
    "            heappush(q, (-diff(x+1, y+1), x+1, y+1))\n",
    "        \n",
    "        return ans / len(classes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        sl = SortedList(classes, key=lambda x: (x[0] + 1) / (x[1] + 1) - x[0] / x[1])\n",
    "        while extraStudents:\n",
    "            p, t = sl.pop()\n",
    "            sl.add([p + 1, t + 1])\n",
    "            extraStudents -= 1\n",
    "        return sum(map(lambda x: x[0] / x[1], sl)) / len(sl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Entry:\n",
    "    __slots__ = 'p', 't'\n",
    "\n",
    "    def __init__(self, p: int, t: int):\n",
    "        self.p = p\n",
    "        self.t = t\n",
    "\n",
    "    def __lt__(self, b: 'Entry') -> bool:\n",
    "        return (self.t - self.p) * b.t * (b.t + 1) > (b.t - b.p) * self.t * (self.t + 1)\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        h = [Entry(*c) for c in classes]\n",
    "        heapify(h)\n",
    "        for _ in range(extraStudents):\n",
    "            heapreplace(h, Entry(h[0].p + 1, h[0].t + 1))\n",
    "        return sum(e.p / e.t for e in h) / len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        diff = lambda x, y: (x + 1) / (y + 1) - x / y\n",
    "        \n",
    "        q = list()\n",
    "        ans = 0\n",
    "        for x, y in classes:\n",
    "            ans += x / y\n",
    "            q.append((-diff(x, y), x, y))\n",
    "        \n",
    "        heapq.heapify(q)\n",
    "        \n",
    "        for _ in range(extraStudents):\n",
    "            d, x, y = heapq.heappop(q)\n",
    "            ans += -d\n",
    "            heapq.heappush(q, (-diff(x + 1, y + 1), x + 1, y + 1))\n",
    "        \n",
    "        return ans / len(classes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 优先队列\n",
    "    # https://leetcode.cn/problems/maximum-average-pass-ratio/solutions/655148/zui-da-ping-jun-tong-guo-lu-by-zerotrac2-84br/\n",
    "    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n",
    "        diff = lambda x, y: (x + 1) / (y + 1) - x / y\n",
    "        \n",
    "        q = list()\n",
    "        ans = 0.0\n",
    "        for x, y in classes:\n",
    "            ans += x / y\n",
    "            # python 中的优先队列是小根堆，所以要对增加量取相反数，达到大根堆的效果\n",
    "            q.append((-diff(x, y), x, y))\n",
    "        \n",
    "        heapq.heapify(q)\n",
    "        \n",
    "        for _ in range(extraStudents):\n",
    "            d, x, y = heapq.heappop(q)\n",
    "            ans += -d\n",
    "            heapq.heappush(q, (-diff(x + 1, y + 1), x + 1, y + 1))\n",
    "        \n",
    "        return ans / len(classes)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
